<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
   "http://www.w3.org/TR/html4/strict.dtd">
<HTML>
   <HEAD>
   	  <link rel="stylesheet" type="text/css" href="phyml+m3l.css">
      <TITLE>M3L</TITLE>
   </HEAD>
      
<BODY>

<p><a href='http://www.uoregon.edu/~joet/'><small>Thornton Lab</small></a> | <a href='http://evolution.uoregon.edu/'><small>IE^2</small></a> | <a href='http://uoregon.edu/'><small>University of Oregon</small></a></p>
<h1>M3L</h1>
<hr>
<p>M3L is a forked extension to <a href="http://www.atgc-montpellier.fr/phyml/">PhyML version 3.0</a>.  M3L provides several analysis tools that are unavailable in PhyML (or anywhere else, for that matter): 
<ol>
<li>A multiple branch length mixture model of heterotachy (<a href="http://mbe.oxfordjournals.org/content/25/6/1054.full.pdf">Kolaczkowski and Thornton, MBE 2008</a>)</li>
<li>Simultaneous optimization of all free parameters, including branch lengths, using the BFGS algorithm.</li>
<li>Optimization of topology and all free parameters, using simulated thermal annealing.</li> 
<li>Empirical Bayesian estimation of posterior probabilities of clades (see <a href="http://mbe.oxfordjournals.org/content/24/9/2108.short">Kolaczkowski and Thornton, MBE 2007</a>)</li>
</ol>
</p>


<div class="divYellow">
<h2>Download M3L</h2>


<a href="http://code.google.com/p/m3l/source/checkout">
<img src="google_icon.png" width=64 border=0 align=center>
</a>
<a href="http://code.google.com/p/m3l/source/checkout">Go to the Google Code repository</a>
</p>

<p>
<small>
The source code is written in C.  Tested using the following software tools: <strong>gcc</strong> version 4.2.1 (Apple Inc. build 5574), with hardware target = i686-apple-darwin9.
<strong>aclocal</strong> version 1.10, <strong>GNU Make</strong> version 3.81, and <strong>GNU Autoconf</strong> version 2.61.
</small>
</p>


</div>

<hr>

<h3>1. A multiple branch length mixture model of heterotachy (<a href="http://mbe.oxfordjournals.org/content/25/6/1054.full.pdf">Kolaczkowski and Thornton, MBE 2008</a>)</h3>
<p>
The branch length mixture model calculates the likelihood of a phylogeny at 
each site in a given sequence alignment as a weighted sum over multiple 
independent branch length sets; weights and branch lengths can be inferred 
from the given sequence data. 
 Under most conditions, the mixed branch length model improves phylogenetic 
 accuracy compared to other homotachous and heterotachous models.  This model 
 should not be confused with other heterotachous models, such as the gamma model 
 [see <a href="http://www.springerlink.com/content/t7k1m86q68854142/">Yang (1994)</a>]
  or the covarion model [see <a href="http://www.springerlink.com/content/127etdjqcuahtg17/">Penny et al. (2001)</a>].  Unlike those models,
   the mixed branch length model relaxes the assumption that the ratio 
   of branch lengths remains constant across sites.
</p>

<h4>Using the mixture model:</h4>
<p>To enable the mixed branch length model, use the command-line option <strong>--bl_mixtures N</strong>, where N is the number of mixtures > 1.  
We strongly suggest you disable the gamma-distributed model when using the mixture model.  In other words, please use <strong>--nclasses 1</strong> in combination with <strong>--bl_mixtures</strong>.  The optimized ML tree will report the mixture of branch lengths using the following format:</p>

<code>b:[l1,l2,...,lN]</code>

<p>where <code>b</code> is the branch label, and <code>l1,l2,...,lN</code> are the unique lengths for each of the N branch length mixtures.  The weights of each mixture are reported during the optimization process; the final ML weights are reported in the PhyML *stats* file, along with all other ML values.</p>

</p>

<hr>

<h3>2. Simultaneous optimization of all free parameters using BFGS.</h3>
<p>Nearly all software for maximum likelihood phylogenetic inference (including PhyML) optimizes branch lengths and all other free parameters using an approach we call "Unimax," in which parameters are optimized sequentially one-at-a-time.
Unimax assumes that the ML value for each parameter can be found without considering the likelihood function for other parameters.  
We implemented an alternative optimization algorithm, called Mulitmax (based on the BFGS algorithm), in which all free parameters are simulateously optimized.  Our results (publication pending) show that Multimax finds higher-likelihood trees in many cases.</p>

<h4>Using Multimax:</h4>

<p>To use Multimax, specify the command-line option <strong>--opt_algorithm 1</strong>.  (By default, PhyML uses Unimax: <strong>--opt_algorithm 0</strong>.)  The performance of Multimax can be tuned using the optional commands <strong>--bfgs_stepsize</strong> and <strong>lnsearch_stepmax</strong>.</p>

<ul>
<li><strong>--bfgs_stepsize num</strong> controls the size of the region over which to calculate the functional gradient of the likelihood function. This area = (2 * <strong>num</strong>) * n, where n is the number of free parameters and <strong>num</strong> is the user-specified value. The default value for <strong>num</strong> is 0.001. Depending on your dataset, good values for <strong>num</strong> can range from 0.001 to 1.0.</li>
<li><strong>--lnsearch_stepmax num</strong> controls the maximum step size for the line search step. After Multimax calculates derivates, it performs a line search in some multidimensional direction, using a maximum step of <strong>num</strong>. The default value is 0.01. Depending on your dataset, good values for <strong>num</strong> can range from 0.001 to 1.0.
</li>

</ul>

<hr>

<h3>3. Optimization of topology and all free parameters using simulated thermal annealing.</h3>
<p>
Traditional hill-climbing optimization algorithms (including both Unimax and Multimax, as discussed above in 2.) can struggle to escape local
 optima when searching over extremely rugged multi-parameterized likelihood landscapes.  The problem is that greedy optimization algorithms
 cannot travel across "valleys" in the likelihood landscape, potentially necessary to reach the globally-maximum likelihood optimum.
M3L implements a method to optimize 
the topology, branch lengths, and model parameters using simulated thermal annealing (STA) 
[see <a href="http://www.comp.nus.edu.sg/~cs5206/2009/Lectures/L13/KGV83-SA.pdf">Kirkpatrick (1983)</a>, 
<a href="http://www.springerlink.com/index/R8316332T1U15773.pdf">Kirkpatrick (1984)</a>, 
and <a href="http://mbe.oxfordjournals.org/cgi/content/abstract/25/6/1054">Kolaczkowski (2008)</a>].  Although STA can 
yield extremely excellent results, STA is computationally demanding and can require hours, 
days, (even weeks!) to find an ML tree.  Given these time constraints, we suggest you first optimize your tree using simpler methods (like Unimax or Multimax).  STA is provided here for experimental purposes.
</p>

<h4>Using STA:</h4>

<p>To use STA, specify the following command-line option <strong>--opt_algorithm 2</strong>.  The performance of STA can be tuned using a large collection of optional command-line parameters:</p>

<ul>
<li><strong>--sa_iters_per_stage N</strong>: STA will perform N iterations at each stage in the cooling schedule.  At each iteration, STA randomly perturbs several (or all) free parameters.  The probability of perturbing a particular parameter is specified by its perturbation probability (see --sa_prob_X).</li>
<li><strong>--sa_num_anneal_stages N</strong>: STA performs N stages in the total cooling schedule.</li>
<li><strong>--sa_temp_end N</strong>: STA will end when the temperature reaches N.</li>
<li><strong>--sa_temp_start N</strong>: STA starts with the system temperature initialized to N.</li>
<li><strong>--sa_scale_temp N</strong>: (experimental) STA will scale the starting system temperature such that it provides a good estimate of the ruggedness of the likelihood landscape.  This estimate is calculated by sampling X randomly pertrubed parameter combinations, where X equals the value of the option sa_iters_per_stage..</li>
<li><strong>--sa_set_back N</strong>: When STA accepts an uphill proposal, it will rollback the counter on iteration/stage by N iterations.  This option is useful when one stage in the cooling schedule is particular fruitful for finding uphill proposals; by setting back the counter, STA can remain in this stage longer.</li>
<li><strong>--sa_stop_early N</strong>: If N=1, then STA will stop if there was no likelihood improvement during the last temperature stage.</li>

<li><strong>--sa_max_X N</strong>: This is a collection of commands to specify the maximum step size for different types of parameters.  X can equal 'brlen', 'pinvar', 'gamma', 'kappa', 'lambda', 'blprop', 'pi', 'rr', and 'emig'.  For example, <strong>--sa_max_brlen 0.1</strong> will constrain all branch length perturbations to be <= 0.1 subs/site.  This means that a branch with length 1.4 subs/site could be perturbed, in a single STA iteration, to have a new value in range [1.3, 1.5].</li>

<li><strong>--sa_prob_X N</strong>: This is a collection of commands to specify the perturbation probability for different types of parameters.  X can equal 'nni', 'spr', 'brlen', 'gamma', 'kappa', 'lambda', 'rr', 'blprop', 'topology', 'pinvar', 'pi', 'emig'.  The value <strong>N</strong> must be in the range [0.0,1.0].  For example, <strong>--sa_prob_brlen 0.7</strong> means that branch lengths will be perturbed in about 70% of the STA iterations.  <strong>--sa_prob_topology 0.1</strong> means that the topology will be rearranged in about 10% of iterations.  <strong>--sa_prob_nni</strong> and <strong>--sa_prob_spr</strong> control the probability of making NNI and SPR moves in the case that the topology is perturbed.</li>

</ul>

<hr>

<h3>4. Empirical Bayes estimation of posterior probabilities of clades (see <a href="http://mbe.oxfordjournals.org/content/24/9/2108.short">Kolaczkowski and Thornton, MBE 2007</a>)</h3>
<p>
Posterior probability (PP) can be a useful metric to estimate the statistical support for the existence
of a phylogenetic clade.  However, simulation studies have shown that when PPs are estimated 
using a Bayesian MCMC strategy that integrates over branch length uncertainty, 
PPs can significantly diverge from their expected values had the branch lengths been known in advance.
Alternatively, an empirical Bayesian strategy that fixes branch lengths at their maximum likelihood values 
is more accurate at estimating the posterior probability of clades. </p>
<p> Phylogenetic practicioners traditionally use the software package 
<a href="http://mrbayes.csit.fsu.edu/">Mr. Bayes</a> to perform MCMC sampling 
and compute posterior probabilities [see <a href="http://bioinformatics.oxfordjournals.org/cgi/content/abstract/19/12/1572">Ronquist and Huelsenbeck (2003)</a>].
Unfortunately, Mr. Bayes does not support a sampling scheme 
in which we can calculate the ML value of branch lengths while integrating
 over uncertainty about other parameters.  Out of necessity, we 
 implemented such an "empirical Bayes" strategy in M3L.  Combined with 
 the previous features of PhyML, you can now use M3L as a single 
 tool to estimate bootstrap values, approximate likelihood ratios (aLRT), and posterior probability values.
</p>

<h4>Using EB:</h4>
<p>To use EB, specify the following command-line option: <strong>-b -5</strong>.  (The <strong>-b</strong> flag is used in PhyML to specify the type of clade support to be calculated.  For example, <strong>-b -1</strong> tells PhyML to calculate aLRT values.)  Also, indicate the number of generations to run the EB procedure, using the command: <strong>--eb_ngens N</strong>, where N is the number of generations.  At each generation, M3L will randomly perturb the topology and then optimize all branch lengths and free parameters using the optimization algorithm specified by the command <strong>--opt_algorithm</strong>.  Keep in mind that time-consuming optimization algorithms (like STA) should probably not be used with EB.</p>

<hr>

<p>
<h3>Thanks, and Disclaimer. . .</h3>
We hope you find M3L useful.  However, be aware that we do not have a large team
 of software developers.  We are providing this software as a resource to the research 
 community, but without the promise of support.  If you have questions, or find software bugs (!), 
 please do not hesitate to contact us.</p>

<hr>
<p><small>Last Modified: November 17, 2011</small>
<br>
<small>by <a href="http://www.victorhansonsmith.com">Victor Hanson-Smith</a></small></p>

<script type="text/javascript">
var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
</script>
<script type="text/javascript">
try {
var pageTracker = _gat._getTracker("UA-12041494-1");
pageTracker._trackPageview();
} catch(err) {}</script>

</BODY>
</HTML>
